
appears to be an extensive variable (i.e., one
that grows linearly with the system size). These
variables are nonextensive in the randomized
networks. The existence of such variables may
be a unifying property of evolved or designed
systems. The decrease of the concentration C
with randomized network size S (Fig. 3) qual-
itatively agrees with exact results (2, 26)on
Erdos-Renyi random graphs (random graphs
that preserve only the number of nodes and
edges of the real network) in which C ⬃ 1/S.In
general, the larger the network is, the more
significant the motifs tend to become. This
trend can also be seen in Table 1 by comparing
networks of different sizes. The network motif
detection algorithm appears to be effective even
for rather small networks (on the order of 100
edges). This is because three- or four-node sub-
graphs occur in large numbers even in small
networks. Furthermore, our approach is not
sensitive to data errors; for example, the sets of
significant network motifs do not change in any
of the networks upon addition, removal, or
rearrangement of 20% of the edges at random.
In information-processing networks, the
motifs may have specific functions as elemen-
tary computational circuits (11). More general-
ly, they may be interpreted as structures that
arise because of the special constraints under
which the network has evolved (27). It is of
value to detect and understand network motifs
in order to gain insight into their dynamical
behavior and to define classes of networks and
network homologies. Our approach can be
readily generalized to any type of network,
including those with multiple “colors” of edges
or nodes. It would be fascinating to see what
types of motifs occur in other networks and to
understand the processes that yield given motifs
during network evolution.
References and Notes
1. S. H. Strogatz, Nature 410, 268 (2001).
2. B. Bollobas, Random Graphs (Academic, London, 1985).
3. D. Watts, S. Strogatz, Nature 393, 440 (1998).
4. A.-L. Baraba´si, R. Albert, Science 286, 509 (1999).
5. M. Newman, Proc. Natl. Acad. Sci. U.S.A. 98, 404
(2001).
6. H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, A. L.
Barabasi, Nature 407, 651 (2000).
7. R. F. Cancho, C. Janssen, R. V. Sole, Phys. Rev. E 64,
046119 (2001).
8. R. F. Cancho, R. V. Sole, Proc. R. Soc. London Ser. B
268, 2261 (2001).
9. L. Amaral, A. Scala, M. Barthelemy, H. Stanley, Proc.
Natl. Acad. Sci. U.S.A. 97, 11149 (2000).
10. B. Huberman, L. Adamic, Nature 401, 131 (1999).
11. S. Shen-Orr, R. Milo, S. Mangan, U. Alon, Nature
Genet. 31, 64 (2002).
12. P. Holland, S. Leinhardt, in Sociological Methodol-
ogy, D. Heise, Ed. ( Jossey-Bass, San Francisco,
1975), pp. 1– 45.
13. S. Wasserman, K. Faust, Social Network Analysis
(Cambridge Univ. Press, New York, 1994).
14. N. Guelzim, S. Bottani, P. Bourgine, F. Kepes, Nature
Genet. 31, 60 (2002).
15. M. Newman, S. Strogatz, D. Watts, Phys. Rev. E 64,
6118 (2001).
16. S. Maslov, K. Sneppen, Science 296, 910 (2002).
17. The randomized networks used for detecting three-
node motifs preserve the numbers of incoming, outgo-
ing, and double edges with both incoming and outgoing
arrows for each node. The randomized networks used
for detecting four-node motifs preserve the above char-
acteristics as well as the numbers of all 13 three-node
subgraphs as in the real network. Algorithms for con-
structing these randomized network ensembles are de-
scribed (18). Additional information is available at
www.weizmann.ac.il/mcb/UriAlon.
18. Methods are available as supporting material on Sci-
ence Online.
19. D. Thieffry, A. M. Huerta, E. Perez-Rueda, J. Collado-
Vides, Bioessays 20, 433 (1998).
20. M. C. Costanzo et al., Nucleic Acids Res. 29,75
(2001).
21. J. Cohen, F. Briand, C. Newman, Community Food
Webs: Data and Theory (Springer, Berlin, 1990).
22. R. Williams, N. Martinez, Nature 404, 180 (2000).
23. S. Pimm, J. Lawton, J. Cohen, Nature 350, 669
(1991).
24. J. White, E. Southgate, J. Thomson, S. Brenner, Philos.
Trans. R. Soc. London Ser. B 314, 1 (1986).
25. F. Brglez, D. Bryan, K. Kozminski, Proc. IEEE Int. Symp.
Circuits Syst., 1929 (1989).
26. In Erdos-Renyi randomized networks with a fixed
connectivity (2), the concentration of a subgraph
with n nodes and k edges scales with network size as
C ⬃ S
n–k–1
(thus, C ⬃ 1/S for the feedforward loop of
Fig. 3 where n ⫽ k ⫽ 3). The sole exception in Table
1 in which C should not vanish at large S is the
three-chain pattern in food webs where n ⫽ 3 and
k ⫽ 2.
27. D. Callaway, J. Hopcroft, J. Kleinberg, M. Newman, S.
Strogatz, Phys. Rev. E 64, 041902 (2001).
28. We thank S. Maslov and K. Sneppen for valuable
discussions. We thank J. Collado-Vides, N. Mar-
tinez, R. Govindan, R. Durbin, L. Amaral, R. Cancho,
S. Maslov, and K. Sneppen for kindly providing data,
as well as D. Alon, E. Domany, M. Elowitz, I. Kanter,
O. Hobart, M. Naor, D. Mukamel, A. Murray, S.
Quake, R. Raz, M. Reigl, M. Surette, K. Sneppen, P.
Sternberg, E. Winfree, and all members of our lab
for comments. We thank Caltech and the Aspen
Center for Physics for their hospitality during part
of this work. We acknowledge support from the
Israel Science Foundation, the Human Frontier Sci-
ence Program, and the Minerva Foundation.
Supporting Online Material
www.sciencemag.org/cgi/content/full/298/5594/824/DC1
Methods
Table S1
1 May 2002; accepted 10 September 2002
Progression of Vertebrate Limb
Development Through
SHH-Mediated Counteraction of
GLI3
Pascal te Welscher,
1
Aime´e Zuniga,
1
Sanne Kuijper,
2
Thijs Drenth,
1
Hans J. Goedemans,
1
Frits Meijlink,
2
Rolf Zeller
1
*
Distal limb development and specification of digit identities in tetrapods are
under the control of a mesenchymal organizer called the polarizing region. Sonic
Hedgehog (SHH) is the morphogenetic signal produced by the polarizing region
in the posterior limb bud. Ectopic anterior SHH signaling induces digit dupli-
cations and has been suspected as a major cause underlying congenital mal-
formations that result in digit polydactyly. Here, we report that the polydactyly
of Gli3-deficient mice arises independently of SHH signaling. Disruption of one
or both Gli3 alleles in mouse embryos lacking Shh progressively restores limb
distal development and digit formation. Our genetic analysis indicates that SHH
signaling counteracts GLI3-mediated repression of key regulator genes, cell
survival, and distal progression of limb bud development.
The Hedgehog (Hh) signaling pathway con-
trols many key developmental processes dur-
ing animal embryogenesis (1). In Drosophila
embryos, all known functions of Hh signaling
are mediated by the transcriptional effector
Cubitus interruptus (Ci) (2). Several ho-
mologs of Hh and Ci have been identified in
higher vertebrates. In particular, Sonic
Hedgehog (SHH) and the Ci homolog GLI3
are required for vertebrate limb development
(3– 6). GLI3 acts first during the initiation of
limb bud development and before the activa-
tion of SHH signaling in posterior restriction
of the basic helix-loop-helix transcription
factor dHAND. dHAND in turn prevents
Gli3 expression from spreading posteriorly
(Fig. 1A, panel 1) (7). In addition, GLI3
restricts the SHH-independent early expres-
sion of 5⬘HoxD genes and Gremlin to the
posterior mesenchyme (8). Subsequently,
dHAND functions in the activation of Shh
expression (9). Limb bud morphogenesis is
then controlled by reciprocal interactions of
two signaling centers (Fig. 1A, panel 2): the
polarizing region, an instructive organizer lo-
cated in the posterior limb bud mesenchyme,
and the apical ectodermal ridge (AER). SHH
signaling by the polarizing region in combi-
nation with bone morphogenetic proteins
1
Department of Developmental Biology, Faculty of
Biology, Utrecht University, Padualaan 8, NL-3584 CH
Utrecht, Netherlands.
2
Hubrecht Laboratorium, Upp-
salalaan 8, NL-3584 CT Utrecht, Netherlands.
*To whom correspondence should be addressed. E-
mail: R.Zeller@bio.uu.nl
R EPORTS
www.sciencemag.org SCIENCE VOL 298 25 OCTOBER 2002 827
on February 4, 2013www.sciencemag.orgDownloaded from